package com.study.algorithm;


import java.util.HashMap;
import java.util.Map;

/**
 * @Author tanglingyu
 * @Date: 2021/07/16/ 10:55
 * @Description:初级算法之数组
 */
public class BaseArrayAlgorithm {

  public static void main(String[] args) {
    removeDuplicates(new int[]{1, 1, 2, 3});
    maxProfit(new int[]{7, 1, 5, 3, 6, 4});
    rotate(new int[]{7, 1, 5, 3, 6, 4}, 2);
    moveZeroes(new int[]{0, 1, 0, 3, 12});
    twoSum(new int[]{3, 2, 4}, 6);
    System.out.println(isValidSudoku(new char[][]{
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}}));
    rotate(new int[][]{
        {5, 1, 9, 11},
        {2, 4, 8, 10},
        {13, 3, 6, 7},
        {15, 14, 12, 16}});
  }

  private static int removeDuplicates(int[] nums) {
    //删除数组中的重复项 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
    int i = 0;
    for (int j = 1; j < nums.length; ++j) {
      if (nums[i] != nums[j]) {
        i++;
        nums[i] = nums[j];
      }
    }
    return i + 1;
  }

  private static int maxProfit(int[] prices) {
    //买卖股票的最佳时机 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
    int total = 0;
    for (int i = 0; i < prices.length - 1; i++) {
      //原数组中如果后一个减去前一个是正数，说明是上涨的，
      //我们就要累加，否则就不累加
      total += Math.max(prices[i + 1] - prices[i], 0);
    }
    return total;
  }

  private static void rotate(int nums[], int k) {
    //旋转数组 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
    int length = nums.length;
    int temp[] = new int[length];
    //把原数组值放到一个临时数组中，
    for (int i = 0; i < length; i++) {
      temp[i] = nums[i];
    }
    //然后在把临时数组的值重新放到原数组，并且往右移动k位
    for (int i = 0; i < length; i++) {
      nums[(i + k) % length] = temp[i];
    }
  }

  private static void moveZeroes(int[] nums) {
    //移动0 双指针解法https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2ba4i/
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
      //只要不为0就往前挪
      if (nums[j] != 0) {
        //i指向的值和j指向的值交换
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
      }
    }
  }

  private static int[] twoSum(int[] nums, int target) {
    //两数之和 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2jrse/
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      if (m.get(target - nums[i]) != null) {
        return new int[]{m.get(target - nums[i]), i};
      }
      m.put(nums[i], i);
    }
    return new int[]{0, 0};
  }

  private static boolean isValidSudoku(char board[][]) {
    //有效的数独 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
    int length = board.length;
    //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
    //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字4
    int line[][] = new int[length][length];
    int column[][] = new int[length][length];
    int cell[][] = new int[length][length];
    for (int i = 0; i < length; ++i) {
      for (int j = 0; j < length; ++j) {
        //如果还没有填数字，直接跳过
        if (board[i][j] == '.') {
          continue;
        }
        //num是当前格子的数字
        int num = board[i][j] - '0' - 1;
        //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
        int k = i / 3 * 3 + j / 3;
        //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
        //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
        if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0) {
          return false;
        }
        //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
        line[i][num] = column[j][num] = cell[k][num] = 1;
      }
    }
    return true;
  }

  private static void rotate(int[][] matrix) {
    //旋转数组 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
    int length = matrix.length;
    //先上下交换
    for (int i = 0; i < length / 2; i++) {
      int temp[] = matrix[i];
      matrix[i] = matrix[length - i - 1];
      matrix[length - i - 1] = temp;
    }
    //在按照对角线交换
    for (int i = 0; i < length; ++i) {
      for (int j = i + 1; j < length; ++j) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
      }
    }
  }
}
